/*
 * @Author: Bubblemilk 
 * @Date: 2023-01-29 23:19:29
 * @LastEditors: Bubblemilk 
 * @LastEditTime: 2023-02-04 17:05:49
 * @FilePath: \code\cpp\priority_queue\priority_queue.hpp
 */
#pragma once
#include <vector>

namespace wyd
{
    //仿函数
    template <class T>
    class less
    {
        bool operator() (const T& val1, const T& val2) const
        {
            return val1 < val2;
        }
    };

    template <class T>
    class greater
    {
        bool operator() (const T& val1, const T& val2) const
        {
            return val1 > val2;
        }
    };

    template <class T, class Container = std::vector<T>, class Compare = less<T>>
    class priority_queue
    {
    public:
        priority_queue() {}

        template <class InputIterator>
        proority_queue(InputIterator first, InputIterator last)
            : _con(first, last)
        {
            for (size_t i = (_con.size()-2); i>=0; --i)
            {
                adjust_down(i);
            }
        }

        /**
         * @description: 压入队列
         * @param {T&} value
         * @return {void}
         */        
        void push(const T& value)
        {
            _con.push_back(value);
            adjust_up(_con.size() - 1);
        }

        /**
         * @description: 出队列
         * @return {void}
         */        
        void pop()
        {
            swap(_con.front(), _con.back());
            _con.pop_back();
            adjust_down(0);
        }

        /**
         * @description: 优先队列的大小
         * @return {size_t}
         */        
        size_t size() const 
        {
            return _con.size();
        }

        /**
         * @description: 取队头元素
         * @return {const T&} 返回队头元素
         */        
        const T& top() const 
        {
            return _con.front();
        }

        /**
         * @description: 判断是否为空
         * @return {bool} 为空返回true
         */        
        bool empty()
        {
            return _con.empty();
        }


    private:

        /**
         * @description: 堆向上调整
         * @param {size_t} child
         * @return {void}
         */
        void adjust_up(size_t child)
        {
            Compare _com;
            size_t parent = (child-1) >> 1;
            while (child > 0)
            {
                if (_com(_con[child],_con[parent]))
                {
                    swap(_con[child],_con[parent]);
                    child = parent;
                    parent = (child - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
        }

        void adjust_down(size_t parent)
        {
            Compare com;
            size_t child = parent * 2 + 1;

            while (child < _con.size())
            {
                if (child+1 < _con.size() && com(_con[child], _con[child+1]))
                {
                    ++child;
                }

                if ( com(_con[child], _con[parent]) )
                {
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

    private:
        Container _con;
    };
}